package queen;

import javax.swing.tree.TreeNode;
import java.lang.reflect.Array;
import java.util.*;

public class 钥匙和房间 {
    public static void main(String[] args) {

    }

    static class Solution {
        boolean[] vis;
        int num = 0;

        //BFS
        public boolean BFScanVisitAllRooms(List<List<Integer>> rooms) {
            int n = rooms.size(), num = 0;
//            创建一个布尔数组，用于记录已经访问过的点
            boolean[] vis = new boolean[n];
//            创建队列，BFS的好基友
            Queue<Integer> que = new LinkedList<>();
            vis[0] = true;    //初始化数组
            que.offer(0);//向队列装入第一个节点

            while (!que.isEmpty()) {  //选取队列首个节点开始搜索
                int x = que.poll();
                num++;
                for (int m : rooms.get(x)) {
                    if (!vis[m]) {
                        que.offer(m);
                        vis[m] = true;
                    }
                }
            }
            return num == n;

        }

        public boolean DFScanVisitAllRooms(List<List<Integer>> rooms) {
            int n = rooms.size();
//          创建一个布尔数组，用于记录已经访问过的点
            dfs(rooms, 0);
            return num == n;
        }

        public void dfs(List<List<Integer>> rooms, int x) {
            vis[x] = true;
            num++;
            for (int m : rooms.get(x)) {
                if (!vis[m]) {
                    dfs(rooms, m);
                }
            }
        }

    }


}
